#include <stdio.h>
#include <stdlib.h>

struct listNode
{
	char data;
	struct listNode *nextPtr;
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert(ListNodePtr *sPtr, char value);
char delete(ListNodePtr *sPtr, char value);
int isEmpty(ListNodePtr sPtr);
void printList(ListNodePtr currPtr);
void instructions(void);

int main(void)
{
	ListNodePtr startPtr = NULL;
	int choice;
	char item;

	instructions();
	printf("?");
	scanf("%d", &choice);

	while(choice !=3)
	{
		switch(choice)
		{
			case 1:
			printf("Enter a character: ");
			scanf("\n%c", &item);
			insert(&startPtr, item);
			printList(startPtr);
			break;

			case 2:
			if(!isEmpty(startPtr))
			{
				printf("Enter character to be deleted: ");
				scanf("\n%c", &item);

				if(delete(&startPtr, item))
				{
					printf("%c deleted.\n", item);
					printList(startPtr);
				}
				else
					printf("%c not found.\n", item);
			}
			else
				printf("List is empty.\n");
			break;

			default:
			printf("Invalid choice.\n");
			instructions();
		}

		printf("?");
		scanf("%d", &choice);
	}

	printf("End.\n");
	return 0;

}

void instructions(void)
{
	printf("Enter your choice:\n"
	    "   1 to insert an element into the list.\n"
	    "   2 to delete an element from the list.\n"
	    "   3 to end.\n");
}

void insert(ListNodePtr *sPtr, char value)
{
	ListNodePtr newPtr;
	ListNodePtr prevPtr;
	ListNodePtr currPtr;

	newPtr = malloc(sizeof(ListNode));

	if(newPtr !=NULL)
	{
		newPtr -> data = value;
		newPtr -> nextPtr = NULL;

		prevPtr = NULL;
		currPtr = *sPtr;

		while(currPtr != NULL && value >currPtr -> data)
		{
			prevPtr = currPtr;
			currPtr = currPtr ->nextPtr;
		}

		if(prevPtr == NULL)
		{
			newPtr -> nextPtr = *sPtr;
			*sPtr = newPtr;
		}
		else
		{
			prevPtr -> nextPtr = newPtr;
			newPtr -> nextPtr = currPtr;
		}
	}
	else
	{
		printf("%c not inserted. No memory avaliable.\n");
	}
}

char delete(ListNodePtr *sPtr, char value)
{
	ListNodePtr tempPtr;
	ListNodePtr prevPtr;
	ListNodePtr currPtr;

	if(value == (*sPtr) -> data)
	{
		tempPtr = *sPtr;
		*sPtr = (*sPtr) -> nextPtr;
		free(tempPtr);
		return value;
	}
	else
	{
		prevPtr = *sPtr;
		currPtr = (*sPtr) -> nextPtr;

		while(currPtr != NULL && currPtr -> data != value)
		{
			prevPtr = currPtr;
			currPtr = currPtr ->nextPtr;
		}

		if(currPtr != NULL)
		{
			tempPtr = currPtr;
			prevPtr -> nextPtr = currPtr -> nextPtr;
			free(tempPtr);
			return value;
		}
	}
	return 0;
}

int isEmpty(ListNodePtr sPtr)
{
	return sPtr == NULL;
}

void printList(ListNodePtr currPtr)
{
	if(currPtr == NULL)
	{
		printf("List is empty.\n");
	}
	else
	{
		printf("The list is: \n");
		while(currPtr != NULL)
		{
			printf("%c  ", currPtr -> data);
			currPtr = currPtr ->nextPtr;
		}
		printf("NULL\n");
	}
}